Computer architectures which include a plurality of network devices connected to a common data bus are well known in the art. Examples of such architectures include local area networks (LAN), computer servers, radio communication system repeater sites, etc.. Each of the foregoing examples require a bus access protocol which conforms to a rigorous set of requirements. In particular, design complexity, mean access time and transmission efficiency are all critical parameters which must be optimized for each application.
Mean access time represents an average time interval in which the network devices are able to send their respective messages out onto the data bus. In certain applications, the mean access time may be a critical requirement, as some of the devices might be quickly buffering messages to be sent across the bus. Without a properly chosen design, extended mean access times might result in device buffers being over run (i.e., while device is waiting for the bus), and hence lost data.
Transmission efficiency is generally related to the mean access time parameter, and describes the systems overall ability to distribute bus access privileges among the requesting devices. A system with high transmission efficiency is able to grant bus requests without excessive message buffering at any one of the requesting devices. Of course, as system complexity increases, and the number of network devices similarly increase, transmission efficiency is both more difficult to insure, and more critical to system performance. For example, in very busy systems where the bus is used often, access to the bus is often the limiting factor which determines how much information/data can be processed. An inefficient access protocol may require higher data rates, wider bandwidths, and more expressive components.
FIG. 1 shows a simplified block diagram of a data bus access system 100, which is well known in the art. Network devices 101-104 are coupled in parallel to data bus 105. Bus access (i.e., BUSY) line 106 is an optional feature which is sometimes used to show the status bus access privileges to each of the devices.
As an illustration of how the system 100 shown in FIG. 1 operates, FIG. 2 shows a timing diagram 200 illustrating the bus access methodology commonly used in today's systems. Each of the network devices is configured to poll the bus (i.e., check to see if the bus is available for transmission) at distinct polling periods 201. These polling periods represent periodically recurring events which take place once every polling interval 202. That is for the access scheme shown in FIG. 2, each of the network devices polls the data bus exactly once during a single polling interval (e.g., between times 203 and 204). It should be noted that the polling periods must be staggered in some fashion to prevent simultaneous polling of the data bus by multiple network devices. It should be further noted that the polling intervals for each device need not be identical (as they are in FIG. 2), but such an implementation represents a complex system design.
In order to show the shortcomings of the aforementioned access methodology, FIG. 3 shows a simplified timing diagram 300 which exemplifies a typical problem in the prior art access protocols. At time 301, D3 (i.e., device 3) begins sending message 302 on the data bus. At time 303, the conclusion of message 302, the bus becomes available for another device (including D3, if required) to access the bus. Subsequently, at time 304, device 2 sends message 305 on the data bus. Message 305 might be of such a length to completely span the polling interval (i.e., interval which, if the bus were available, would permit each device to poll at least once). At time 306, message 305 is completed, and the bus becomes available. Subsequently, D3 sends another message on to the bus, as it is the next device to poll the bus. Upon completion of this message, DEVICE 2 polls and accesses the bus, as it is the device whose polling period occurs first subsequent to when the bus becomes available. The foregoing pattern may repeat indefinitely so long as devices 2 and 3 have messages to be sent on the bus. Of course, this scheme is undesirable, since it denies bus access to device 1, irrespective of whether or not it has a message to be sent.
Accordingly, there exists a need for a data bus access protocol which is not constrained by the aforementioned shortcomings. In particular, a simple bus access protocol which prevents any one, or more, device(s) from monopolizing the bus would be an improvement over the prior art. This scheme would further provide a deterministic access sequence, such that the order of access can be determined from previous access patterns. Such a sequence would advantageously ensure finite, bounded, access times for each device in the system, while allowing priority scanning for particular devices, if desired. A system which employed such a scheme might therefore be well suited for use as a real time system controller in a radio communication system.